package lhc.alg.top100;

/**
 * description: https://leetcode.cn/problems/number-of-longest-increasing-subsequence/
 *  300提的拓展题  673. 最长递增子序列的个数  动归。。。。 O(n^2) O(n)
 *  还有方法2 用二分+前缀和 更难。。
 * author: hongchen.liao
 * date:  2022/9/1
 */
public class _637_Number_of_Longest_Increasing_Subsequence {

    class Solution {
        public int findNumberOfLIS(int[] nums) {
            int n = nums.length, maxLen = 0, ans = 0;
            int[] dp = new int[n];
            int[] cnt = new int[n];
            for(int i = 0; i < n; i++){
                dp[i] = 1;
                cnt[i] = 1;
                for(int j = 0; j < i; j++){
                    if(nums[i] > nums[j]){
                        if(dp[j] + 1 > dp[i]){
                            dp[i] = dp[j] + 1;
                            cnt[i] = cnt[j];
                        }else if(dp[j]+1 == dp[i]){
                            cnt[i] += cnt[j];
                        }
                    }
                }
                if(dp[i] > maxLen){
                    maxLen = dp[i];
                    ans = cnt[i];
                }else if(dp[i] == maxLen){
                    ans += cnt[i];
                }
            }
            return ans;
        }
    }

}
